package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024/4/6 21:23
 */
public class T1031maxSumTwoNoOverlap {
    /*
给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠 子数组 中元素的最大和，长度分别为 firstLen 和 secondLen 。
长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。
子数组是数组的一个 连续 部分。
示例 1：
输入：nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：
输入：nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：
输入：nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
     */
    /*
    解题思路：
    1、
     */

    @Test
    public void t1() {
        System.out.println(maxSumTwoNoOverlap(new int[]{0, 6, 5, 2, 2, 5, 1, 9, 4}, 1, 2));//20
        System.out.println(maxSumTwoNoOverlap(new int[]{3, 8, 1, 3, 2, 1, 8, 9, 0}, 3, 2));//29
        System.out.println(maxSumTwoNoOverlap(new int[]{2, 1, 5, 6, 0, 9, 5, 0, 3, 8}, 4, 3));//31
        System.out.println(maxSumTwoNoOverlap(new int[]{12, 8, 12, 18, 19, 10, 17, 20, 6, 8, 13, 1, 19, 11, 5}, 3, 6));//131
    }

    /*
    解决了问题，但是速度太慢，
    其中第二个大for循环是属于重复的，可以做标记的
     */
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(doSumMax(nums, firstLen, secondLen), doSumMax(nums, secondLen, firstLen));
    }

    private int doSumMax(int[] nums, int firstLen, int secondLen) {
        int max = 0;
        int firstTail = nums.length - (firstLen + secondLen);
        for (int firstI = 0; firstI <= firstTail; firstI++) {
            int firstTemp = 0;
            for (int i = firstI; i < firstI + firstLen; i++) {
                firstTemp += nums[i];
            }
            int secondTail = nums.length - secondLen;
            for (int secondI = firstI + firstLen; secondI <= secondTail; secondI++) {
                int secondTemp = 0;
                for (int i = secondI; i < secondI + secondLen; i++) {
                    secondTemp += nums[i];
                }
                max = Math.max(max, (firstTemp + secondTemp));
            }
        }
        return max;
    }


    /*
    官方答案
     */
    public int maxSumTwoNoOverlap1(int[] nums, int firstLen, int secondLen) {
        return Math.max(help(nums, firstLen, secondLen), help(nums, secondLen, firstLen));
    }

    public int help(int[] nums, int firstLen, int secondLen) {
        int suml = 0;
        for (int i = 0; i < firstLen; ++i) {
            suml += nums[i];
        }
        int maxSumL = suml;
        int sumr = 0;
        for (int i = firstLen; i < firstLen + secondLen; ++i) {
            sumr += nums[i];
        }
        int res = maxSumL + sumr;
        for (int i = firstLen + secondLen, j = firstLen; i < nums.length; ++i, ++j) {
            suml += nums[j] - nums[j - firstLen];
            maxSumL = Math.max(maxSumL, suml);
            sumr += nums[i] - nums[i - secondLen];
            res = Math.max(res, maxSumL + sumr);
        }
        return res;
    }

}
